#include"List.h"
//打印函数
void SLPrint(ListNode* head)
{
    ListNode* pcur = head;
    while (pcur) {
        printf("%d->",pcur->val);
        pcur = pcur->next;
    }
    printf("NULL\n");
}
//5——链表分割
ListNode* partition(ListNode* pHead, int x) {
        //创建大小链表，并申请动态空间
        ListNode* lesshead,* lesstail;
        lesshead = lesstail = (ListNode*)malloc(sizeof(ListNode));
        ListNode* morehead,* moretail;
        morehead = moretail = (ListNode*)malloc(sizeof(ListNode));
        //遍历原链表，分别插入大小链表
        ListNode* pcur = pHead;
        while(pcur)
        {
            //插入小链表
            if(pcur->val < x)
            {
                lesstail->next = pcur;
                lesstail = lesstail->next;
            }
            //插入大链表
            else
            {
                moretail->next = pcur;
                moretail = moretail->next;
            }
            pcur = pcur->next;
        }
        //链表遍历结束后，要将新链表的尾节点的下一位置空
        moretail->next = NULL;
        //将大小链表连接起来
        lesstail->next = morehead->next;
        //最后先把新链表的头节点保存下来，然后再释放并置空大小节点的动态空间
        ListNode* ret = lesshead->next;
        free(lesshead);
        lesshead = NULL;
        free(morehead);
        morehead = NULL;
        return ret;
    }
//6——链表的回文结构
//方法一：将链表中的数据插入到数组中进行双指针判断回文结构
//但是此方法要申请数组空间，空复较高，为O（n）
bool chkPalindrome(ListNode* A) {
        //定义数组，以供后续用来存放数组
       int arr[900];//可以初始化，也可以不初始化，因为后续会进行赋值。
       //遍历原链表，将链表数据存入数组中
        ListNode* pcur = A;
        int i = 0;
        while (pcur) {
            arr[i++] = pcur->val;
            pcur = pcur->next;
        }
        //然后在数组中用"双指针"判断回文结构
        int left = 0;
        int right = i-1;
        while (left < right) {
            if(arr[left] != arr[right])
            {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
//方法二：找中间节点，将后半点逆置，然后与原链表对比。最优方案。
bool chkPalindrome2(ListNode* A) {
        //1 找到中间节点
        ListNode* mid = middleNode(A);
        //2 逆置后半段链表
        ListNode* newNode = reverseList(mid);
        //比较链表
        ListNode* l1 = A,* l2 = newNode;
        while (l2) {
            if(l1->val != l2->val)
            {
                return false;
            }
            l1 = l1->next;
            l2 = l2->next;
        }
        return true;
    }
//7——返回倒数第 k 个节点中的数值
int kthToLast(struct ListNode* head, int k) {
    //空链表直接传空
    if(head == NULL)
        return 0;
    //将链表逆置一下
    ListNode* newNode = reverseList(head);
    //直接找第二个节点
    //定义 pcur 等于新链表的头结点
    ListNode* pcur = newNode;
    for(int i = 1;i < k;i++)
    {
        pcur = pcur->next;
    }
    return pcur->val;
}
//8——相交链表
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    //1.遍历两个链表，找两链表差值gap
    int sizeA = 0,sizeB = 0;
    ListNode* l1 = headA,* l2 = headB;
    while(l1)
    {
        sizeA++;
        l1 = l1->next;
    }
    while(l2)
    {
        sizeB++;
        l2 = l2->next;
    }
    int gap = abs(sizeA - sizeB);
    //2.长链表先走 gap 个节点，使两链表同长
    //找到长节点
    ListNode* longlist = headA;
    ListNode* shortlist = headB;
    if(sizeA < sizeB)
    {
        longlist = headB;
        shortlist = headA;
    }
    //让长节点走 gap 个节点
    while(gap--)
    {
        longlist = longlist->next;
    }
    //3.同步遍历比较两链表
    while(longlist && shortlist)
    {
        if(longlist == shortlist)
        {
            return longlist;
        }
        longlist = longlist->next;
        shortlist = shortlist->next;
    }return NULL;
}
//9——环状链表
//较为简单，重在理解快慢指针为何会相遇,快指针走2，慢指针走1
bool hasCycle(struct ListNode *head) {
    //直接定义快慢指针
    ListNode* fast = head,* slow = head;
    //不断遍历，直至相遇，返回 true,若 fast 或者 fast->next 为空，则跳出循环
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            return true;
        }
        
    }
    return false;
}
//10——环状链表 2——找入环点
struct ListNode *detectCycle(struct ListNode *head) {
    //快慢指针判断是否为带环
    ListNode* fast = head,* slow = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        //如果相遇了,则必定可以找到入环点
        if(slow == fast)
        {
            ListNode* pcur = head;
            while(pcur != slow)
            {
                pcur = pcur->next;
                slow = slow->next;
            }
            return pcur;
        }
    }
    //若不为环，则返回空
    return NULL;
}
//随机链表的复制

